/**
 * 和为S的两个数字
 *
 * 输入一个递增排序的数组array和一个数字S，在数组中查找两个数，使得他们的和正好是S，
 * 如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。
 *
 * 数据范围:
 * 0<=len(array)<=105
 * 1<=array[i]<=106
 */

import java.util.ArrayList;

/**
 * 因为数组是有序的, 所以我们只要取两边的数进行相加就可以了, 要是结果小于 sum
 * 说明左边需要移动, 大于则说明有右边需要移动, 相等就已经找到结果了
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {
    public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
        int left = 0, right = array.length - 1;
        while (left < right) {
            int tmp = array[left] + array[right];
            if (tmp < sum) {
                left++;
            } else if (tmp > sum) {
                right--;
            } else {
                ArrayList<Integer> result = new ArrayList<>();
                result.add(array[left]);
                result.add(array[right]);
                return result;
            }
        }
        return new ArrayList<>();
    }
}